//给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。 
//
// 返回符合要求的 最少分割次数 。 
//
// 
// 
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：1
//解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
// 
//
// 示例 2： 
//
// 
//输入：s = "a"
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：s = "ab"
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 2000 
// s 仅由小写英文字母组成 
// 
//
// 
//
// 
// 注意：本题与主站 132 题相同： https://leetcode-cn.com/problems/palindrome-partitioning-
//ii/ 
//
// Related Topics 字符串 动态规划 👍 49 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer2_094 {

    public int minCut(String s) {
        int n = s.length();
        boolean[][] g = new boolean[n][n];
        for(int i = n-1; i >=0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(j -i <= 1){
                        g[i][j] = true;
                    } else {
                        g[i][j] = g[i+1][j-1];
                    }
                }
            }
        }
        //dp[i]表示s[0]-s[i]的最少分割次数
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for(int i = 0; i < n; i++){
            if(g[0][i]){
                dp[i] = 0;
            } else {
                for (int j = 0; j < i; j++) {
                    if (g[j+1][i]) {
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }
        }
        return dp[n-1];
    }

    public static void main(String[] args) {
        int aab = new SolutionOffer2_094().minCut("efe");
        System.out.println(aab);
    }


    /**
     * 方法1：递归回溯：超时
     */
    List<String> list = new ArrayList<>();
    int result = Integer.MAX_VALUE;
    public int minCut1(String s) {
        delimiter(s, 0);
        return result;
    }

    private void delimiter(String s, int startIndex){
        if(startIndex == s.length()){
            result = Math.min(result, list.size()-1);
            return;
        }
        for(int i = startIndex; i < s.length(); i++){
            if(isCheck(s.substring(startIndex, i+1))){
                list.add(s.substring(startIndex, i+1));
                delimiter(s, i+1);
                list.remove(list.size()-1);
            }
        }
    }

    private boolean isCheck(String s) {
        int i = 0, j = s.length() -1 ;
        while(i < j){
            if(s.charAt(i) == s.charAt(j)){
                i++;
                j--;
            }else{
                return false;
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
